package main.Q501_600;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Q511_520 {
    public static void main(String[] args) {
        System.out.println("Question511：游戏玩法分析Ⅰ");
        System.out.println("Question512：");
        System.out.println("Question513：找树左下角的值");
        System.out.println("Question514：");
        System.out.println("Question515：在每个树行中找到最大值");
        System.out.println("Question516：最长回文子序列");
        System.out.println("Question517：");
        System.out.println("Question518：零钱兑换Ⅱ");
        int[] arr={1,2,5};
        System.out.println(new Question518().change(5,arr));
        System.out.println("Question519：");
        System.out.println("Question520：检测大写字母");
    }
}

class Question511{
    {
        System.out.println("select player_id,min(event_date) first_login\n" +
                "from Activity\n" +
                "Group By player_id;");
    }
}

class Question513{
    public int findBottomLeftValue(TreeNode root) {
        int result=0;
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size= queue.size();
                List<Integer> list=new ArrayList<>();
                for (int i=0;i<size;i++){
                    TreeNode curNode=queue.poll();
                    list.add(curNode.val);
                    if (curNode.left!=null) queue.add(curNode.left);
                    if (curNode.right!=null) queue.add(curNode.right);
                }
                if (queue.isEmpty()) result=list.get(0);
            }
        }
        return result;
    }
}

class Question515{
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                int max=queue.peek().val;
                for (int i=0;i<size;i++){
                    TreeNode curNode=queue.poll();
                    if (curNode.val>max) max=curNode.val;
                    if (curNode.left!=null) queue.add(curNode.left);
                    if (curNode.right!=null) queue.add(curNode.right);
                }
                list.add(max);
            }
        }
        return list;
    }
}

class Question516{
    public int longestPalindromeSubseq(String s) {
        int max=1,length=s.length();
        char[] str=s.toCharArray();
        int[][] dp=new int[length][length];
        for (int i=length-1;i>=0;i--){
            dp[i][i]=1;
            for (int j=i+1;j<length;j++){
                if (str[i]==str[j]) dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                max=Math.max(max,dp[i][j]);
            }
        }
        return max;
    }
}

class Question518{
    public int process(int curAmount,int[] coins,int start){//递归调用
        if (curAmount==0) return 1;
        else if (curAmount<0) return 0;
        int count=0;
        for (int i=start;i<coins.length;i++){
            count+=process(curAmount-coins[i],coins,i);
        }
        return count;
    }
    public int change(int amount, int[] coins) {
        int length=coins.length;
        int[] dp=new int[amount+1];
        dp[0]=1;
        for (int coin:coins){
            for (int i=coin;i<=amount;i++){
                dp[i]+=dp[i-coin];
            }
        }
        return dp[amount];
    }
}

class Question520{
    public static boolean detectCapitalUse(String word) {
        //第一个字母为大写，则之后只能为大写或小写
        if (word.length()>=2&&Character.toUpperCase(word.charAt(0))==word.charAt(0)){
            int lowerCount=0,upperCount=0;
            for (int i=1;i<word.length();i++){
                if (word.charAt(i)>='a'&&word.charAt(i)<='z') lowerCount++;
                else upperCount++;
            }
            if (lowerCount==0||upperCount==0) return true;
            else return false;
        }
        //第一个字母为小写，则之后只能为小写
        if (word.length()>=2&&Character.toLowerCase(word.charAt(0))==word.charAt(0)){
            for (int i=1;i<word.length();i++) if (word.charAt(i)<'a'||word.charAt(i)>'z') return false;
            return true;
        }
        return true;
    }
}